package com.graph;

/*
 * Taranjeet singh Bhatia
 * Code For Assignment # 4
 * DepthFirstSearch.java class
 */

import java.awt.Dimension;
import java.awt.Point;
import java.util.ArrayList;

import javax.swing.JFrame;

import edu.uci.ics.jung.algorithms.layout.CircleLayout;
import edu.uci.ics.jung.algorithms.layout.Layout;
import edu.uci.ics.jung.graph.Graph;
import edu.uci.ics.jung.graph.SparseMultigraph;
import edu.uci.ics.jung.visualization.BasicVisualizationServer;
import edu.uci.ics.jung.visualization.decorators.ToStringLabeller;
import edu.uci.ics.jung.visualization.renderers.Renderer.VertexLabel.Position;

public class DepthFirstSearch {
	GraphClass g1;
	int[] vertexArray, parent;
	ArrayList<Point> treeEdges = new ArrayList<Point>();
	ArrayList<Point> nonTreeEdges = new ArrayList<Point>();

	DepthFirstSearch(GraphClass g1) {
		this.g1 = g1;
		this.vertexArray = new int[g1.getVertex()];
		this.parent = new int[g1.getVertex()];
		for (int i = 0; i < this.parent.length; i++) {
			this.parent[i] = -1;
		}
		VertexState state[] = new VertexState[g1.getVertex()];

		for (int i = 0; i < g1.getVertex(); i++)
			state[i] = VertexState.White;

		runDFS(0, state);

		// displayGraph(this.nonTreeEdges);
		displayGraph(this.treeEdges);

	}

	private void displayGraph(ArrayList<Point> treeEdges2) {

		Graph<Integer, String> g = new SparseMultigraph<Integer, String>();
		for (int i = 1; i < this.g1.vertex + 1; i++) {
			g.addVertex((Integer) i);
		}
		for (int i = 0; i < treeEdges2.size(); i++) {
			Integer weight = this.g1.getEdgeWeight(treeEdges2.get(i).x,
					treeEdges2.get(i).y);
			g.addEdge(weight.toString(), treeEdges2.get(i).x,
					treeEdges2.get(i).y);
		}

		displayGraph(g);
	}

	private void runDFS(int u, VertexState[] state) {
		state[u] = VertexState.Gray;
		for (int v = 0; v < this.g1.getVertex(); v++) {
			if (this.g1.isEdge(u, v) && state[v] == VertexState.White) {

				this.treeEdges.add(new Point(u, v));
				this.parent[v] = u;
				runDFS(v, state);

			} else if (this.g1.isEdge(u, v) && state[v] == VertexState.Black) {
				this.nonTreeEdges.add(new Point(u, v));
			}

		}
		state[u] = VertexState.Black;

	}

	enum VertexState {
		White, Gray, Black
	}

	public static void displayGraph(Graph<Integer, String> g) {
		System.out.println("The graph g = " + g.toString());

		Layout<Integer, String> layout = new CircleLayout(g);
		layout.setSize(new Dimension(300, 300)); // sets the initial size of the
													// space
		// The BasicVisualizationServer<V,E> is parameterized by the edge types
		BasicVisualizationServer<Integer, String> vv = new BasicVisualizationServer<Integer, String>(
				layout);
		vv.setPreferredSize(new Dimension(350, 350)); // Sets the viewing area
														// size
		vv.getRenderContext().setVertexLabelTransformer(new ToStringLabeller());
		vv.getRenderContext().setEdgeLabelTransformer(new ToStringLabeller());
		vv.getRenderer().getVertexLabelRenderer().setPosition(Position.CNTR);

		JFrame frame = new JFrame("Simple Graph View");
		frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
		frame.getContentPane().add(vv);
		frame.pack();
		frame.setVisible(true);
	}

	public static void displayGraph() {
		Graph<Integer, String> g = new SparseMultigraph<Integer, String>();
		for (int i = 1; i < 6; i++) {
			g.addVertex((Integer) i);
		}
		g.addEdge("e12", 1, 2);
		g.addEdge("e23", 2, 3);
		g.addEdge("e34", 3, 4);
		g.addEdge("e45", 4, 5);
		g.addEdge("e52", 5, 2);
		g.addEdge("e13", 1, 3);
		System.out.println("The graph g = " + g.toString());

		Layout<Integer, String> layout = new CircleLayout(g);
		layout.setSize(new Dimension(300, 300)); // sets the initial size of the
													// space
		// The BasicVisualizationServer<V,E> is parameterized by the edge types
		BasicVisualizationServer<Integer, String> vv = new BasicVisualizationServer<Integer, String>(
				layout);
		vv.setPreferredSize(new Dimension(350, 350)); // Sets the viewing area
														// size
		vv.getRenderContext().setVertexLabelTransformer(new ToStringLabeller());
		vv.getRenderContext().setEdgeLabelTransformer(new ToStringLabeller());
		vv.getRenderer().getVertexLabelRenderer().setPosition(Position.CNTR);

		JFrame frame = new JFrame("Simple Graph View");
		frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
		frame.getContentPane().add(vv);
		frame.pack();
		frame.setVisible(true);

	}

	public static void main(String[] args) {
		// displayGraph();
		GraphClass g1 = new GraphClass(8);
		g1.addEdge(0, 1, 4);
		g1.addEdge(0, 3, 6);
		g1.addEdge(0, 6, 16);
		g1.addEdge(1, 2, 24);
		g1.addEdge(3, 2, 23);
		g1.addEdge(3, 4, 5);
		g1.addEdge(3, 6, 8);
		g1.addEdge(6, 4, 10);
		g1.addEdge(4, 2, 18);
		g1.addEdge(4, 5, 11);
		g1.addEdge(4, 7, 14);
		g1.addEdge(6, 7, 21);
		g1.addEdge(7, 5, 7);
		g1.addEdge(5, 2, 9);

		new DepthFirstSearch(g1);

	}

	public Point find_max_weight_edge(int u, int v) {

		Point p;
		Point p_max = new Point(v, this.parent[v]);

		if (u != this.parent[v]) {

			p = find_max_weight_edge(u, this.parent[v]);
		} else {
			p = new Point(u, v);
		}

		if ((g1.getEdgeWeight(p.x, p.y)) > (g1.getEdgeWeight(p_max.x, p_max.y))) {
			p_max = p;
		}

		// TODO Auto-generated method stub
		return p_max;
	}

	public Point heaviest_edge(Point e, Point w) {
		Point heavyEdge;
		if ((g1.getEdgeWeight(e.x, e.y)) > (g1.getEdgeWeight(w.x, w.y))) {
			heavyEdge = e;
		} else
			heavyEdge = w;
		return heavyEdge;
	}

}
